/**
 * @author 徐楠
 * @date 2022/1/2 21:03
 * @version 1.0
 */

package com.xunan.likou;

public class ArraySplit1 {

    public static void main(String[] args) {

        int[] nums = {1,4,3,2};
        int i = arrayPairSum(nums);
        System.out.println(i);
    }

    public static int arrayPairSum(int[] nums) {


        int[] tmp = new int[nums.length];//新建一个临时数组存放
        mergeSort(nums,0,nums.length-1,tmp);

        int result = 0;
        int numsLength = nums.length;
        for (int i = 0; i < numsLength-1; i++,i++) {
            result += Math.min(nums[i],nums[i+1]);
        }
        return result;
    }

    public static void bubbleSort(int array[]) {
        int temp = 0;
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }


    //归并排序
    public static void merge(int[] arr,int low,int mid,int high,int[] tmp){
        int i = 0;
        int j = low,k = mid+1;  //左边序列和右边序列起始索引
        while(j <= mid && k <= high){
            if(arr[j] < arr[k]){
                tmp[i++] = arr[j++];
            }else{
                tmp[i++] = arr[k++];
            }
        }
        //若左边序列还有剩余，则将其全部拷贝进tmp[]中
        while(j <= mid){
            tmp[i++] = arr[j++];
        }

        while(k <= high){
            tmp[i++] = arr[k++];
        }

        for(int t=0;t<i;t++){
            arr[low+t] = tmp[t];
        }
    }

    public static void mergeSort(int[] arr,int low,int high,int[] tmp){
        if(low<high){
            int mid = (low+high)/2;
            mergeSort(arr,low,mid,tmp); //对左边序列进行归并排序
            mergeSort(arr,mid+1,high,tmp);  //对右边序列进行归并排序
            merge(arr,low,mid,high,tmp);    //合并两个有序序列
        }
    }


}
